package algorithm.dynamic;

import java.util.ArrayList;
import java.util.List;

/**
 * @author bingo
 * @Description
 * @Date 2018/8/31
 */
public class Test {

    private static List<Integer> numberList = new ArrayList<>();


    public static  int  goStairs2(int n){
        if(n==1){
            return  1;

        }
        if(n==2){

            return 2;
        }
        if(numberList.get(n)==-1){
            numberList.set(n,goStairs2(n-1)+goStairs2(n-2));
        }

        return   numberList.get(n);

    }



    public  static  int  goStairs(int n){
        Integer[] a = new Integer[n+1];
        a[1] = 1;
        a[2] = 2;
        for(int i=3;i<=n;i++){
            a[i] = a[i-1]+a[i-2];
        }

        return a[n];
    }

    public static void main(String[] args) {

        int n=45;
        for(int i=0;i<n+1;i++){
            numberList.add(i,-1);
        }
        //System.out.println(GoStairs.goStairs(n));

        System.out.println(GoStairs.goStairs2(n));
    }
}
